<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="QSCRb" id="QSCRb"><span data-lake-id="u8a28e06d" id="u8a28e06d">典型回答</span></h1>
  <p data-lake-id="u15b18aaf" id="u15b18aaf"><span data-lake-id="u9f48e9ec" id="u9f48e9ec">所谓前缀树，也叫字典树，是一种变种的多叉树。</span></p>
  <p data-lake-id="ub4320990" id="ub4320990"><span data-lake-id="uaa760589" id="uaa760589">举个例子：有以下字符串：</span></p>
  <p data-lake-id="u11082702" id="u11082702"><span data-lake-id="u99dfcad1" id="u99dfcad1">abc,bac,bbc,ca，</span></p>
  <p data-lake-id="ufa55ae61" id="ufa55ae61"><span data-lake-id="ubac03c55" id="ubac03c55">通过字典树形成的结构如下所示：</span></p>
  <p data-lake-id="u588742ed" id="u588742ed"><img src="https://cdn.nlark.com/yuque/0/2023/png/719664/1676792969926-ec009095-e7a3-412b-9cfa-60c9734ad4ab.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_13%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u2dac4a65" id="u2dac4a65"><span data-lake-id="u1d9f55c6" id="u1d9f55c6">从上图我们可以看出，通过字典树，在查询的时候，原来的时间复杂度是O(n*m)，优化后的时间复杂度就会变成O(m)。同时，如果有很多字符串，字典树还可以大大减少存储的空间</span></p>
  <p data-lake-id="u0d2e2ced" id="u0d2e2ced"><span data-lake-id="u249433eb" id="u249433eb">字典树的java实现如下所示：</span></p>
  <pre lang="java"><code>
class Trie {

    private Trie[] children;

    private boolean isWord;

    public Trie() {
        this.isWord = false;
        this.children = new Trie[26];
    }
    
    public void insert(String word) {
        Trie next = this;
        for(char c : word.toCharArray()) {
            if(next.children[c - 'a'] == null) {
                next.children[c - 'a'] = new Trie();
            }
            next = next.children[c - 'a'];
        }
        next.isWord = true;
    }
    
    public boolean search(String word) {
        Trie next = this;
        for(char c : word.toCharArray()) {
            if(next.children[c - 'a'] == null) {
                return false;
            }
            next = next.children[c - 'a'];
        }
        return next.isWord;
    }
    
    public boolean startsWith(String prefix) {
        Trie next = this;
        for(char c : prefix.toCharArray()) {
            if(next.children[c - 'a'] == null) {
                return false;
            }
            next = next.children[c - 'a'];
        }
        return true;
    }
}
</code></pre>
  <h1 data-lake-id="qCV54" id="qCV54"><span data-lake-id="ub0309a0e" id="ub0309a0e">知识扩展</span></h1>
  <h2 data-lake-id="WfPT7" id="WfPT7"><span data-lake-id="u11abd209" id="u11abd209">前缀树有哪些应用？</span></h2>
  <h3 data-lake-id="AUTIA" id="AUTIA"><span data-lake-id="u7bc3c9da" id="u7bc3c9da">字符串检索</span></h3>
  <p data-lake-id="ub4016a26" id="ub4016a26"><span data-lake-id="ued5dea78" id="ued5dea78" style="color: rgb(0, 0, 0)">给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。</span></p>
  <h3 data-lake-id="suTqr" id="suTqr"><span data-lake-id="u3a2cd000" id="u3a2cd000">字符串最长公共前缀</span></h3>
  <p data-lake-id="ue7649021" id="ue7649021"><span data-lake-id="u47160258" id="u47160258" class="lake-fontsize-11" style="color: rgb(0, 0, 0)">给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少？</span></p>
  <h3 data-lake-id="fCGYf" id="fCGYf"><span data-lake-id="u143b4b0a" id="u143b4b0a">排序</span></h3>
  <p data-lake-id="u6c712a4e" id="u6c712a4e"><span data-lake-id="uf127532b" id="uf127532b" class="lake-fontsize-11" style="color: rgb(0, 0, 0)">Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果。比如给你N 个互不相同的仅由一个单词构成的英文名，让你将它们按字典序从小到大排序输出。</span></p>
  <h3 data-lake-id="RWHnR" id="RWHnR"><span data-lake-id="ub5cdcdc7" id="ub5cdcdc7" style="color: rgb(0, 0, 0)">作为其他数据结构和算法的辅助结构</span></h3>
  <p data-lake-id="uf307fe60" id="uf307fe60"><span data-lake-id="u1adafb79" id="u1adafb79" style="color: rgb(0, 0, 0)">如后缀树，AC自动机等</span></p>
  <h3 data-lake-id="onmT5" id="onmT5"><span data-lake-id="u24c35c19" id="u24c35c19" style="color: rgb(0, 0, 0)">词频统计</span></h3>
  <p data-lake-id="u4512cfb0" id="u4512cfb0"><span data-lake-id="u28f9dd53" id="u28f9dd53" class="lake-fontsize-11" style="color: rgb(0, 0, 0)">trie树在这里的应用类似哈夫曼树，比如词频统计使用哈希表或者堆都可以，但是如果内存有限，就可以用trie树来压缩空间，因为trie树的公共前缀都是用一个节点保存的。</span></p>
  <h3 data-lake-id="tlVfG" id="tlVfG"><span data-lake-id="u0e00cc42" id="u0e00cc42" style="color: rgb(0, 0, 0)">字符串搜索的前缀匹配</span></h3>
  <p data-lake-id="u9ff36241" id="u9ff36241"><span data-lake-id="u899eff8a" id="u899eff8a" class="lake-fontsize-11" style="color: rgb(0, 0, 0)">trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。</span></p>
 </body>
</html>